package com.qfedu.entity.course15;

import java.util.*;

public class NQueen {

    public static void main(String[] args) {
        NQueen nQueen = new NQueen();
        System.out.println(nQueen.solveNQueens(8));
    }

    /**
     * 入口函数
     */
    public List<List<String>> solveNQueens(int n) {
        char[][] chess = new char[n][n];//初始化数组
        for (int i = 0; i < n; i++)
            for (int j = 0; j < n; j++)
                chess[i][j] = '.';
        List<List<String>> res = new ArrayList<>();
        solve(res, chess, 0);
        return res;
    }

    private void solve(List<List<String>> res, char[][] chess, int row) {
        // 递归出口，最后一行都走完了，说明找到了一组，把它加入到集合res中
        if (row == chess.length) {
            res.add(toList(chess));
            return;
        }
        for (int col = 0; col < chess.length; col++) { //遍历每一列  
            if (valid(chess, row, col)) { // 判断这个位置是否可以放皇后        
                char[][] temp = copy(chess); //数组复制一份              
                temp[row][col] = 'Q';//在当前位置放个皇后                
                solve(res, temp, row + 1); //递归到下一行继续
            }
        }
    }

    private boolean valid(char[][] chess, int row, int col) {
        //判断当前列有没有皇后,因为他是一行一行往下走的，
        //我们只需要检查走过的行数即可，通俗一点就是判断当前
        //坐标位置的上面有没有皇后
        for (int i = 0; i < row; i++) {
            if (chess[i][col] == 'Q') {
                return false;
            }
        }
        //判断当前坐标的右上角有没有皇后
        for (int i = row - 1, j = col + 1; i >= 0 && j < chess.length; i--, j++) {
            if (chess[i][j] == 'Q') {
                return false;
            }
        }
        //判断当前坐标的左上角有没有皇后
        for (int i = row - 1, j = col - 1; i >= 0 && j >= 0; i--, j--) {
            if (chess[i][j] == 'Q') {
                return false;
            }
        }
        return true;
    }

    //把二维数组chess中的数据copy一份
    private char[][] copy(char[][] chess) {
        char[][] temp = new char[chess.length][chess[0].length];
        for (int i = 0; i < chess.length; i++) {
            for (int j = 0; j < chess[0].length; j++) {
                temp[i][j] = chess[i][j];
            }
        }
        return temp;
    }

    //把数组转为list
    private List<String> toList(char[][] chess) {
        List<String> path = new ArrayList<>();
        for (int i = 0; i < chess.length; i++) {
            path.add(new String(chess[i]));
        }
        return path;
    }

    public List<List<String>> solveNQueensWithBacktrack(int n) {
        List<List<String>> solutions = new ArrayList<>();// 用来记录结果的数组
        int[] queens = new int[n];// (i,queens[i])放置皇后
        Arrays.fill(queens, -1);// 初始化为-1
        Set<Integer> columns = new HashSet<>();// columns[i]表示第i列上已经放置了皇后
        Set<Integer> diagonals1 = new HashSet<>();// 表示左上到右下的斜线，同一斜线上行列坐标之差相等
        Set<Integer> diagonals2 = new HashSet<>();// 表示右上到左下的斜线，同一斜线上行列坐标之和相等
        backtrack(solutions, queens, n, 0, columns, diagonals1, diagonals2);// 开始递归
        return solutions;
    }

    //生成最终的结果
    public List<String> generateBoard(int[] queens, int n) {
        List<String> board = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            char[] row = new char[n];
            Arrays.fill(row, '.');
            row[queens[i]] = 'Q';
            board.add(new String(row));
        }
        return board;
    }

    // n表示是n皇后问题；row 表示当前将要填充的行号
    public void backtrack(List<List<String>> solutions, int[] queens, int n, int row, Set<Integer> columns, Set<Integer> diagonals1, Set<Integer> diagonals2) {
        if (row == n) {// 递归出口
            List<String> board = generateBoard(queens, n);
            solutions.add(board);
        } else {
            for (int i = 0; i < n; i++) {// 对于当前的第row行，试图去填充每一列
                if (columns.contains(i)) {
                    continue;
                } // 如果当前列上已经有皇后了，退出此次循环，填充下一列
                int diagonal1 = row - i;// 使用行列坐标只差来表示方向一(左上到右下)的斜线
                if (diagonals1.contains(diagonal1)) {
                    continue;
                } // 如果方向一已经有皇后了，退出此次循环，填充下一列
                int diagonal2 = row + i;// 使用行列坐标只和来表示方向二(右上到左下)的斜线
                if (diagonals2.contains(diagonal2)) {
                    continue;
                } // 如果方向二已经有皇后了，退出此次循环，填充下一列
                // 如果当前位置(row,i)可以放置皇后，更新状态
                queens[row] = i;
                columns.add(i);
                diagonals1.add(diagonal1);
                diagonals2.add(diagonal2);
                //继续遍历下一行
                backtrack(solutions, queens, n, row + 1, columns, diagonals1, diagonals2);
                // 上面的递归完成后，在(row,i)放置皇后对的前提下所有可能已经记录在solutions里面了，复原状态
                queens[row] = -1;
                columns.remove(i);
                diagonals1.remove(diagonal1);
                diagonals2.remove(diagonal2);
            }
        }
    }
}
